package sword_offer;

import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author Synhard
 * @version 1.0
 * @class Code52
 * @description 剑指 Offer 49. 丑数
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 *
 * 示例:
 *
 * 输入: n = 10
 * 输出: 12
 * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 * 说明:  
 *
 * 1 是丑数。
 * n 不超过1690。
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-12 9:22
 */
public class Code52 {
    public static void main(String[] args) {
        System.out.println(nthUglyNumber(11));
    }

    public static int nthUglyNumber(int n) {
        if (n == 1) {
            return 1;
        }
        int[] factors = new int[]{2, 3, 5};
        PriorityQueue<Long> queue = new PriorityQueue<>(Long::compareTo);
        HashSet<Long> set = new HashSet<>();
        queue.add(1L);
        set.add(1L);
        for (int i = 0; i < n - 1; i++) {
            long head = queue.poll();
            for (int j = 0; j < factors.length; j++) {
                if (!set.contains(head * factors[j])) {
                    set.add(head * factors[j]);
                    queue.add(head * factors[j]);
                }
            }
        }
        long res = queue.peek();
        return (int) res;
    }
}

/*
每次取出堆顶元素 x，则 x 是堆中最小的丑数，由于 2x, 3x, 5x 也是丑数，因此将 2x, 3x, 5x 加入堆。

上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。

在排除重复元素的情况下，第 n 次从最小堆中取出的元素即为第 n 个丑数。
 */